package hard.区间问题.划分字母区间;

import java.util.*;


/**
 * @author zhengTao
 * @version 1.0
 * @description: 划分字母区间 ,这题是Demo56的升级版，比Demo56多几个步骤
 * @date 2022/11/23 11:30
 */
public class Demo763 {
    public static void main(String[] args) {
        String s="ababcbacadefegdehijhklij";
        List<Integer> list = partitionLabels(s);
        System.out.println(list);
    }
    public static List<Integer> partitionLabels(String s) {
    Map<Character,int[]> hashMap=new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
            //找出每个元素的起始位置和终止位置
            if(!hashMap.containsKey(s.charAt(i))){
                int[] ints=new int[2];
                int start = s.indexOf(s.charAt(i));
                int end = s.lastIndexOf(s.charAt(i));
                ints[0]=start;
                ints[1]=end;
                hashMap.put(s.charAt(i),ints);
            }
        }
        int[][] res=new int[hashMap.size()][2];
        int length=0;
        //将每个元素的起始位置和终止位置的数组，添加到二维数组里面去
        Set<Map.Entry<Character, int[]>> entries = hashMap.entrySet();
        for (Map.Entry<Character, int[]> entry : entries) {
            res[length++]=entry.getValue();
        }
        //根据起始位置排序，起始位置肯定不同，如果起始位置相同，则按照终止位置从大到小排序
        Arrays.sort(res, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                if(o1[0]==o2[0]){
                   return o1[1]-o2[1];
                }
                return o1[0]-o2[0];
            }
        });
        //合并区间
        List<Integer> resList=new ArrayList<>();
        //只有一个元素，直接返回
        if(res.length==1){
            resList.add(res[0][1]-res[0][0]+1);
            return resList;
        }
        //多个元素合并区间
        for (int i = 1; i < res.length; i++) {
            if(res[i-1][1]>res[i][0]){
                res[i][0]=Math.min(res[i-1][0],res[i][0]);
                res[i][1]=Math.max(res[i-1][1],res[i][1]);
            }else {
                resList.add(res[i-1][1]-res[i-1][0]+1);
            }
        }
        resList.add(res[res.length-1][1]-res[res.length-1][0]+1);
        return resList;
    }
}
